package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class RemoveDuplicatesFromSortedListIi {
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            if (head == null) return null;
            ListNode dummy = new ListNode(-1000,head);
            ListNode prev = dummy;
            ListNode delEnd = null;
            ListNode delStart= new ListNode(-100,dummy);
            while (head!=null){
                if (head.val==prev.val){
                    delEnd = head;
                }else {
                    if (delEnd!=null){
                        delStart.next = delEnd.next;
                        prev = delStart.next;
                        delEnd = null;
                    }else {
                        prev = prev.next;
                        delStart = delStart.next;
                    }

                }
                head = head.next;
            }
            if (delEnd != null){
                delStart.next = null;
            }
            return dummy.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}